/**
 * 每个元素与前一位元素作比较，如果小于前一位就互换位置，直到找到合适自己的位置
*/

const swap = (arr, i, j) => {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

const insertSort = arr => {
  for (let i = 1; i < arr.length; i++) {
    let j = i
    while (j >= 1 && arr[j] < arr[j - 1]) {
      swap(arr, j, j - 1)
      j--
    }
  }
  return arr
}

console.log(insertSort([4, 3, 1, 0, 2]))